\documentclass[11pt,a4paper]{scrartcl}

% Use utf-8 encoding for foreign characters
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}

% For enumeration lists
\usepackage{enumerate}

% Setup for fullpage use
%\usepackage{fullpage}

% More symbols
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{ulsy}

%\usepackage{latexsym}

% Surround parts of graphics with box
\usepackage{boxedminipage}

% Package for including code in the document
%\usepackage{listings}
\usepackage{alltt}

\usepackage{fancyhdr}
\usepackage{lastpage}

% For tables
\usepackage{booktabs}
%\usepackage{tablex}


\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt} %obere Trennlinie entfernen
\fancyfoot[C]{\thepage/\pageref{LastPage}}

\begin{document}

%\maketitle
% Some renewcommand and newcommand
%\renewcommand{\labelenumi}{\alph{enumi})}
%\renewcommand{\labelenumii}{\arabic{enumii}.}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Pp}{\mathcal{P}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\K}{\mathcal{K}}

\include{Titelseite}

\section*{Aufgabe 1}
\begin{minipage}[h!]{0.45\linewidth}
\subsection*{a)}
\begin{align*}
p  &= 11,\; g = 2,\; a = 8\\
sk &= (p, g, a),\; pk = (p, g, h)\\
h  &= g^a \bmod p\\
   &= 2^8 = 3 \bmod 11\\
\Rightarrow\; pk &=(11,\; 2,\; 3)
\end{align*}
\end{minipage}
\begin{minipage}[]{0.45\linewidth}
\subsection*{b)}
\begin{align*}
m &= 5,\; r = 7,\; c = (v, w)\\
v &= g^r \bmod p\\
  &= 2^7 = 7 \bmod 11\\
w &= h^r m \bmod p\\
  &= 3^7 \cdot 5 = 1 \bmod 11\\
\Rightarrow\; c &= (7,\; 1)
\end{align*}
\end{minipage}
\\
\begin{minipage}[t!]{0.45\linewidth}
\subsection*{c)}
\begin{align*}
(c_1&, c_2) = (9, 4)\\
u &= c_1^a \bmod p\\
  &= 9^8 = 3 \bmod 11\\
m &= u^{-1} \cdot m \bmod p\\
\end{align*}
\end{minipage}\\
%\begin{minipage}[b]{0.45\linewidth}
berechne $u^{-1}$ mit dem\\ erweiterten euklidischen Algorithmus:
\begin{center}
$ggt(u, p) = ggt(3, 11)= u^{-1} \cdot 3 + k \cdot 11 = 1$
\end{center}
\begin{minipage}[h!]{0.45\linewidth}
\begin{align*}
&&11 &= 3 \cdot 3 + 2\\
&& 3 &= 1 \cdot 2 + 1\\
&& 2 &= 2 \cdot 1 + 0
\end{align*}
\end{minipage}
\begin{minipage}[]{0.45\linewidth}
\begin{align*}
&&1 &= 3 - (1 \cdot 2)\\
&&  &= 3 - (11 - 3 \cdot 3)\\
&&  &= 4 \cdot 3 - 1 \cdot 11 \bmod 11
\end{align*}
\end{minipage}
\begin{center}
$\Rightarrow$  $u^{-1} = 4 \bmod 11$
\end{center}
Damit ist $m = 4 \cdot 4 = 5 \bmod 11$
%\end{minipage}

\section*{Aufgabe 2}
\subsection*{a)}
\begin{align*}
     c_2 &= h^r m_1       \Leftrightarrow \frac{c_2}{h^r} = m_1 \bmod p\\
 c_2^{'} &= h^{r^{'}} m_2 \Leftrightarrow \frac{c_2^{'}}{h^{r{'}}} = m_2 \bmod p\\
c_2^{''} &= h^{r^{''}} m_1 m_2
          = h^{r^{''}} \frac{c_2}{h^r} \frac{c_2^{'}}{h^{r^{'}}}
          = h^{r{''}-(r + r^{'})} c_2 c_2^{'} \bmod p
\end{align*}
$r^{''}$ ist frei wählbar (eigtl. zufällig), es sei $r^{''} = r + r^{'}$.\\
Damit ist $c_2^{''} = h^{r + r^{'} - (r + r^{'})} c_2 c_2^{'} = c_2 c_2^{'} \bmod p$
\begin{align*}
c_1      &= g^r \bmod p\\
c_1^{'}  &= g^r{'} \bmod p\\
c_1^{''} &= g^r{''} = g^{r + r^{'}} = g^r \cdot g^r{'} = c_1 c_2 \bmod p
\end{align*}
Zum Klartext $m_1 m_2$ ist $(c_1 c_1^{'}, c_2 c_2^{'})$
also ein m\"oglicher Chiffretext.

\subsection*{b)}
Die Erkenntnisse aus a) lassen sich auch bei 3 Chiffretexten anwenden:\\
\\
$c_i = (v_i, w_i), i = 1,.., 3$ für die Klartext $m_i$\\
$c_4 = (v_4, w_4)$ f\"ur den Klartext $m_1 m_2 m_3$
\begin{align*}
r_4 &= r_1 + r_2 + r_3\\
v_4 &= g^{r_4} = g^{r_1} g^{r_2} g^{r_3} = v_1 v_2 v_3 \bmod p\\
	&= 7 \cdot 10 \cdot 9 = 3 \bmod 11\\
w_4 &= w_1 w_2 w_3 \cdot h^{r_4 - (r_1 + r_2 + r_3)} = w_1 w_2 w_3 \bmod p\\
	&= 1 \cdot 5 \cdot 4 = 9 \bmod 11
\end{align*}
Also ist $c_4 = (3, 9)$.

\section*{Aufgabe 3}
$sk = (p, g, a),\; pk=(p, g, h),\;
m \in \mathbb{Z}_p^*,\; C(m) \subseteq \mathbb{Z}_p^* \times \mathbb{Z}_p^*$\\
\\
Sei $b \in C(m_1)$ und $b \in C(m_2)$ mit $m_1 \ne m_2$ und $b=(v, w)$.\\
Bis auf $r$ sind alle Variablen für beide Klartexte gleich.
\begin{align*}
&&v &= g^r = g^{r^{'}} \bmod p\\
&&w &= (g^a)^r m_1 = (g^a)^{r^{'}} m_2 \bmod p\\
\Leftrightarrow &&(g^r)^a m_1 &= (g^{r^{'}})^a m_2 \bmod p\\
\Leftrightarrow && v^a \cdot m_1 &= v^a \cdot m_2 \bmod p\\
\Leftrightarrow && m_1 &= m_2 \bmod p
\end{align*}
Das steht im Widerspruch zur Forderung $m_1 \ne m_2$\\
$\Rightarrow\; C(m_1) \cap C(m_2) = \emptyset$ 

\section*{Aufgabe 4}
Zu $(c_1, c_2)$ erzeuge Klartext-Chiffrepaar $(c_1^{'}, c_2^{'}) = (c_1, 2 c_2)
\ne (c_1, c_2)$\\
\begin{align*}
&&c_1^{'} &= g^{r{'}} = g^r = c_1 \pmod p\\
\\
&&c_2^{'} &= 2c_2 \pmod p\\
\Leftrightarrow&& h^{r^{'}} m^{'} &= 2 (h^{r} m) \pmod p\\
\Leftrightarrow&& (g^a)^{r^{'}} m^{'} &= 2 ((g^a)^{r} m) \pmod p\\
\Leftrightarrow&& (g^{r^{'}})^a m^{'} &= 2 (g^{r})^a m \pmod p\\
\Leftrightarrow&& (c_1)^a m^{'} &= 2 (c_1)^a m \pmod p\\
\Leftrightarrow&& m^{'} &= 2 m \pmod p\\
\Leftrightarrow&& 2^{-1} m^{'} &= m \pmod p
\end{align*}
Der Angreifer erzeugt den Klartext zu $(c_1, 2 c_2)$, multipliziert ihn
mit dem Inversen von $2 \pmod p$ und erh\"alt $m$.

\end{document}
